package graphic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author ZhangyiA
 * @describe:
 * @date 2021/06/17
 * c 4 4          // 顶点个数 , 边的个数
 * v 0 2
 * v 1 2
 * v 2 6
 * v 3 6
 * e 0 1 2
 * e 0 2 2
 * e 1 3 2
 * e 2 3 3
 */



public class Graph {

    private int min_sup;
    private int node_num;
    private int edge_num;
    Map<Integer , ArrayList<Edge>> label_edges; // 根据边标签 , 将边聚类
    Map<Integer , ArrayList<Integer>> label_vertex; // 根据顶点标签 , 将顶点聚类
    private HashMap<Integer , Integer> old_mapping_new; // 旧顶点 - 新顶点 的映射 , 用于重构边
    private HashMap<Integer , Integer> new_mapping_old; // 新顶点 - 旧顶点 的映射 , 用于最后的还原工作
    public Vertex[] vertices; // 存放重构后的顶点
    public Edge[] edges; // 重构后的边集合
    public int[] head;

    public Graph(){
        this.old_mapping_new = new HashMap<>();
        this.new_mapping_old = new HashMap<>();
    }

    public void rebuildGraph(){
        // 1. 删除非频繁的顶点
        delNonFreqVertex();
        // 2. 重构顶点编号
        rebuildVertex();
        // 3. 删除非频繁的边
        delNonFreqEdge();
        // 4. 重构边 ， 进一步删除冗余边， 存在 频繁边连接的顶点式非频繁的 ， 那么这种情况下的边是无意义的
        rebuildEdge();

        // 输出重构后的图
        /*for(int i = 0 ; i < node_num ; i ++){
            for(int j = head[i] ; j != -1 ; j = edges[j].getNext()){
                System.out.println(edges[j].toString());
            }
        }*/

        /*for(int i = 0 ; i < node_num ; i ++){
            System.out.println("i = " + i + "  degree = " + vertices[i].degree);
        }*/

        // 输出新旧顶点之间的映射关系
        /*for(Map.Entry<Integer , Integer> entry : new_mapping_old.entrySet()){
            System.out.println(entry.getKey() + "  " + entry.getValue());
        }*/

//        for(int i = 0 ; i < edges.length ; i ++){
//            System.out.println(i + " " + edges[i].toString());
//        }

        System.out.println("class Graph --> step1: Graph data preprocessing");
        System.out.println("node_num = " + node_num + "  edge_num = " + edge_num + "\n");
    }

    /*public void rebuildGraph(){
        System.out.println("------------顶点为删除之前-------------");
        for(Map.Entry<Integer , ArrayList<Integer>> entry : label_vertex.entrySet()){
            System.out.println(entry.getKey());
            for(int num : entry.getValue()){
                System.out.print(num + "   ");
            }
            System.out.println();
        }
        // 1. 删除非频繁的顶点
        delNonFreqVertex();
        System.out.println("------------顶点为删除之后-------------");
        for(Map.Entry<Integer , ArrayList<Integer>> entry : label_vertex.entrySet()){
            System.out.println(entry.getKey());
            for(int num : entry.getValue()){
                System.out.print(num + "  ");
            }
            System.out.println();
        }
        // 2. 重构顶点编号
        rebuildVertex();
        System.out.println("------------顶点重构之后-------------");
        for(Map.Entry<Integer , Integer> entry : new_mapping_old.entrySet()){
            System.out.println(entry.getKey() + "    " + entry.getValue());
        }
        // 3. 删除非频繁的边
        System.out.println("------------边删除之前-------------");
        for(Map.Entry<Integer , ArrayList<Edge>> entry : label_edges.entrySet()){
            System.out.println(entry.getKey());
            for(Edge edge : entry.getValue()){
                System.out.println(edge.toString());
            }
            System.out.println();
        }
        delNonFreqEdge();

        // 4. 重构边 ， 进一步删除冗余边， 存在 频繁边连接的顶点式非频繁的 ， 那么这种情况下的边是无意义的
        rebuildEdge();
        for(Edge edge : edges){
            System.out.println(edge.toString());
        }
    }*/

    public void setLabel_Vertex(Map<Integer , ArrayList<Integer>> label_vertex){
        this.label_vertex = label_vertex;
    }

    public void setLabel_Edges(Map<Integer , ArrayList<Edge>> label_edges){
        this.label_edges = label_edges;
    }

    public void delNonFreqEdge(){
        Set<Map.Entry<Integer , ArrayList<Edge>>> set = label_edges.entrySet();
        set.removeIf(entry -> entry.getValue().size() < 2 * min_sup); // 同一个标签有正反两条边 , 因此需要 2 倍
    }

    public void delNonFreqVertex(){
        Set<Map.Entry<Integer , ArrayList<Integer>>> set = label_vertex.entrySet();
        set.removeIf(entry -> entry.getValue().size() < min_sup);
    }

    public void rebuildVertex(){
        int count = 0;
        for(Map.Entry<Integer , ArrayList<Integer>> entry : label_vertex.entrySet()){
            count += entry.getValue().size();
        }
        vertices = new Vertex[count];
        head = new int[count];

        Arrays.fill(head , -1);
        sortVertexWithLabel(); // 根据标签的频率排序
        for(Map.Entry<Integer , ArrayList<Integer>> entry : label_vertex.entrySet()){
            int label = entry.getKey();
            for(int val : entry.getValue()){
                vertices[node_num] = new Vertex(node_num , label , node_num); // 重新将顶点 设置编号 ，从 0 开始，旧编号是 val  ， 按照顶点的标签 重新排序
                new_mapping_old.put(node_num , val);
                old_mapping_new.put(val , node_num);
                node_num ++;
            }
        }
    }

    public void sortVertexWithLabel(){
        List<Map.Entry<Integer , ArrayList<Integer>>> list = new ArrayList<>(label_vertex.entrySet());
        Collections.sort(list , (o1 , o2) -> o2.getValue().size() - o1.getValue().size());
        label_vertex.clear();
        label_vertex =  new LinkedHashMap<Integer, ArrayList<Integer>>(){{
            list.forEach(mm -> {
                put(mm.getKey() , mm.getValue());
            });
        }};
    }

    public void rebuildEdge(){
        int count = 0;
        for(Map.Entry<Integer , ArrayList<Edge>> entry : label_edges.entrySet()){
            count += entry.getValue().size();
        }
        edges = new Edge[count];

        sortEdgeWithLabel();
        for(Map.Entry<Integer , ArrayList<Edge>> entry : label_edges.entrySet()){
            for(Edge edge : entry.getValue()){
                // 如果一条边的 起点或者终点 不是频繁顶点 该条边无意义
                if(!old_mapping_new.containsKey(edge.getVertexFrom()) || !old_mapping_new.containsKey(edge.getVertexTo())){
                    continue;
                }
                int newFrom = old_mapping_new.get(edge.getVertexFrom());
                int newTo = old_mapping_new.get(edge.getVertexTo());
                edge.setVertexFrom(newFrom);
                edge.setVertexTo(newTo);
                edge.setNext(head[newFrom]);
                edge.setId(edge_num); // 保存边的标号

                vertices[newFrom].degree ++;
                edges[edge_num] = edge;
                head[newFrom] = edge_num ++;
            }
        }
        edges = Arrays.copyOf(edges , edge_num); // 因为中间有很多无意义的边
    }

    public void sortEdgeWithLabel(){
        List<Map.Entry<Integer , ArrayList<Edge>>> list = new ArrayList<>(label_edges.entrySet());
        Collections.sort(list , (o1 , o2) -> o2.getValue().size() - o1.getValue().size());
        label_edges.clear();
        label_edges =  new LinkedHashMap<Integer , ArrayList<Edge>>(){{
            list.forEach(mm -> {
                put(mm.getKey() , mm.getValue());
            });
        }};
    }

    public int getMin_sup() {
        return min_sup;
    }

    public void setMin_sup(int min_sup) {
        this.min_sup = min_sup;
    }

    public int getNode_num() {
        return node_num;
    }

    public int getEdge_num() {
        return edge_num;
    }
}
